// search all elements of a string string1 into another bigger string string2
// and return the block with minimum size containing all the elements from string1
// string s1 = "ABC"
// string s2 = "BDAEXCCYBZABXPQC"
// The minimum size block in s2 is 5 CYBZA from s[6] to s[10]

#include<iostream>
//#include<string.h>
//#include<stdio.h>
//#include<math.h>
using namespace std;

class hash
{
	private:
	int *a;
	int kamplete;
	int value;
	
	public:
	hash(string s);
	void push(char c);
	void pop(char c);
	int complete();
	int hlength()
	{
		return value;
	}
	~hash()
	{
		delete a;
	}	
};

hash:: hash(string s)
{
	a = new int[256];
	for(int i=0; i<256; i++)
	a[i] = -1;
	
	for(int i=0; i<s.length(); i++)
	{
		if(a[s[i]]==-1)
		value++;
		a[s[i]] = 0;
	}
}

void hash::push(char c)
{
	if(a[c] == -1)
	return;
	if(a[c] == 0)
	kamplete++;
	a[c]++;
}

void hash::pop(char c)
{
	if(a[c] == -1)
	return;
	if(a[c] == 1)
	kamplete--;
	if(a[c] == 0)
	{
		cout << "\nError, popping an item without existing.Exiting Program Now.\n";
		return;
	}
	a[c]--;
}

int hash::complete()
{
	if(kamplete == value)
		return 1;
	return 0;
}

int stringsearch(string s1, string s2, int& a, int& b);

int main()
{
	string s1 = "abce";
	string s2 = "ahsokdeepakchachaankitbhaixyapqrbcbqartureisscvblabghaslavbvabdabvbascxnzadsf";
	//cin >> s1;
	//cin >> s2;
	int i=0;
	int j=0;
	cout << "\nThe given strings are:\n" << s1 << "\n" << s2;
	int k = stringsearch(s1, s2, i, j);
	if(k==0)
	return 0;
	
	cout << "\nThe minimum block in second string containing all";
	cout << " element from first string is:" << endl;
	cout << i << "," << j << endl;
	cout << "The Block containing first string is:" << endl;
	for(int a = i; a <= j; a++)
	cout << s2[a];
	cout << endl;
	return 0;
}


int stringsearch(string s1, string s2, int&a, int&b)
{
	if(s1.length() == s2.length())
	{
		if(s1 != s2)
		{
			cout << "\nNo Match Found\n";
			return 0;
		}
		cout << "\nBoth the strings are equal\n";
		b = s2.length() -1;
		a=0;
		return 0;
	}
	
	hash *h = new hash(s1);
	int i=0;
	int j=0;
	if(h->hlength() > s2.length())
	{
		cout << "\nSecond String can not contain first string.\n";
		return 0;
	}
	int k=s2.length()+1;
	while(i < s2.length())
	{
		while(!h->complete() && i < s2.length())
		{
			h->push(s2[i]);
			i++;
		}
		if(k>i-j)
		{
			k = i-j;
			a = j;
			b = i-1;
		}
		while(h->complete())
		{
			h->pop(s2[j]);
			j++;
		}
		if(k > i+1-j)
		{
			k = i+1-j;
			a = j-1;
			b = i-1;
		}
	}
	if(k == s2.length()+1)
	{
		return 0;
	}
	return 1;
}
